use once_cell::sync::Lazy;
use std::sync::Mutex;
use utils::math::miller_rabin;

fn min_edge_prime_num_iter(
    start_layer: u128,
    init_prime_count: usize,
) -> impl Iterator<Item = (u128, usize, u32)> {
    (start_layer..)
        .into_iter()
        .map(move |n| {
            let base = (2 * n - 1).pow(2);
            (1..4)
                .into_iter()
                .map(move |x| base - (2 * n - 2) * x)
                .map(|x| miller_rabin(x))
                .filter(|&x| x)
                .count()
        })
        .enumerate()
        .scan(
            init_prime_count,
            move |prime_count_sum, (layer, prime_count)| {
                let layer = layer as u128 + start_layer;
                *prime_count_sum += prime_count;
                let total = 4 * layer - 3;
                let rate = (*prime_count_sum as f32 / total as f32 * 100.0).floor() as u32;
                Some((layer, *prime_count_sum, rate))
            },
        )
}

//layer, prime_count_sum, rate
static PRIME_CACHE: Lazy<Mutex<Vec<(u128, usize, u32)>>> = Lazy::new(|| Mutex::new(Vec::new()));
pub fn min_edge_prime_num(number: u32) -> String {
    let mut cache = PRIME_CACHE.lock().unwrap();
    let mut rate_cached = cache.last().map(|(_, _, rate)| *rate).unwrap_or(101);
    let cache_idx = match cache.binary_search_by(|(_, _, rate)| number.cmp(rate)) {
        Ok(x) => Some(x),
        Err(x) => {
            if x == 0 {
                None
            } else {
                Some(x - 1)
            }
        }
    };
    let (layer_cache, prime_count_sum_cache, _) = match cache_idx {
        Some(x) => *cache.get(x).unwrap(),
        None => (1, 0, 0),
    };
    for (layer, prime_sum, rate) in min_edge_prime_num_iter(layer_cache + 1, prime_count_sum_cache)
    {
        if rate < rate_cached {
            rate_cached = rate;
            cache.push((layer, prime_sum, rate))
        }
        if rate < number {
            return format!("{},{prime_sum}", layer * 2 - 1);
        }
    }
    unreachable!()
}
